#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// binary search tree node
struct BSTreeNode
{
	int value;
	struct BSTreeNode *leftChild;
	struct BSTreeNode *rightChild;
};

void addBSTreeNode(struct BSTreeNode **ppRoot/*double pointer to the root*/, int new_value);
void printBSTree(ofstream *fout, struct BSTreeNode *root, int level);
void treeToLinkedList(struct BSTreeNode **ppHead, struct BSTreeNode **ppTail, struct BSTreeNode *root);

int main() {
	ifstream fin ("tree_to_linked_list.in");
	ofstream fout ("tree_to_linked_list.out");
	int in;
	struct BSTreeNode *root = NULL, *head = NULL, *tail = NULL, *node = NULL;

	if(fin.good() == false)
	{
		cerr << "file open failed" << endl;
		return 0;
	}

	while(true)
	{
		if(fin.eof())
			break;

		fin >> in;

		addBSTreeNode(&root, in);
	}

	printBSTree(&fout, root, 0);

	fout << endl;

	treeToLinkedList(&head, &tail, root);

	for(node = head; node != NULL; node = node->rightChild)
	{
		fout << node->value << " ";
	}
	fout << endl;

	for(node = tail; node != NULL; node = node->leftChild)
	{
		fout << node->value << " ";
	}
	fout << endl;

	return 0;
}

void addBSTreeNode(struct BSTreeNode **ppRoot/*double pointer to the root*/, int new_value)
{
	if(*ppRoot == NULL)
	{
		*ppRoot = new struct BSTreeNode();
		(*ppRoot)->value = new_value;
		
		return;
	}

	if(new_value == (*ppRoot)->value)
	{
		return;
	}
	else if(new_value < (*ppRoot)->value)
	{
		addBSTreeNode(&(*ppRoot)->leftChild, new_value);
	}
	else
	{
		addBSTreeNode(&(*ppRoot)->rightChild, new_value);
	}
}

void printBSTree(ofstream *pFout, struct BSTreeNode *root, int level)
{
	if(root == NULL)
		return;

	printBSTree(pFout, root->leftChild, level + 1);

	int i;

	for(i = 0; i < level; i ++)
		(*pFout) << "\t";

	(*pFout) << root->value << endl;

	printBSTree(pFout, root->rightChild, level + 1);
}

void treeToLinkedList(struct BSTreeNode **ppHead, struct BSTreeNode **ppTail, struct BSTreeNode *root)
{
	struct BSTreeNode *ltemp, *rtemp;

	if(root == NULL)
	{
		(*ppHead) = NULL;
		(*ppTail) = NULL;
		return;
	}

	treeToLinkedList(ppHead, &ltemp, root->leftChild);
	treeToLinkedList(&rtemp, ppTail, root->rightChild);

	if(*ppHead == NULL)
	{
		(*ppHead) = root;
		root->leftChild = NULL;
	}
	else
	{
		root->leftChild = ltemp;
		ltemp->rightChild = root;
	}

	if(*ppTail == NULL)
	{
		(*ppTail) = root;
		root->rightChild = NULL;
	}
	else
	{
		root->rightChild = rtemp;
		rtemp->leftChild = root;
	}
}